package leetcode101_xqzhao

// TODO 打家劫舍 【-】 动态规划 [经典]

func rob(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}

	// 定义状态数组
	dp := make([]int, n)
	// 定义初始状态
	dp[0] = nums[0]
	dp[1] = max9(nums[0], nums[1])
	// 状态转移方程
	for i := 2; i < n; i++ {
		dp[i] = max9(dp[i-1], nums[i]+dp[i-2])
	}
	return dp[n-1]
}

func max9(x, y int) int {
	if x > y {
		return x
	}
	return y
}
